#include"DynamicArray.h"
#include<iostream>


DynamicArray::DynamicArray(int capacity):size(0),capacity(capacity)
{
    array = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
    delete[] a.array;
}

void DynamicArray::operator=(const DynamicArray &a)
{
    delete[] array;
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }

}

DynamicArray::~DynamicArray()
{
    delete[] array;
}

void DynamicArray::InsertTail(const ElementType &element)
{
    //扩容
    if(size>=capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size;i++)
        {
            newP[i] = array[i];
        }
        delete[] array;
        array = newP;
    }

    array[size++] = element;
}

void DynamicArray::show()
{
    for (int i = 0; i < size;i++)
    {
        std::cout << array[i] << " " ;
    }
    std::cout << std::endl;
}

void DynamicArray::RemoveByIndex(DynamicArray &a, int index)
{
    if(index<0||index>a.size)
    {
        std::cout << "非法位置" << std::endl;
        return;
    }
    for (int i = index; i < a.size-1;i++)
    {
        a.array[i] = a.array[i + 1];
    }
    a.size--;
}

void DynamicArray::RemoveByValue(DynamicArray &a, ElementType element)
{
    for (int i = 0; i < a.size;i++)
    {
        if(a.array[i]==element)
        {
            DynamicArray::RemoveByIndex(a, i);
            i--;
        }
    }
}

DynamicArray DynamicArray::FindByElement(const DynamicArray &a, ElementType element)
{
    for (int i = 0; i < a.size;i++)
    {
        if(a.array[i]==element)
        {
            return a.array[i];
        }
    }
        return ElementType();
}
void FastSort(DynamicArray &a,int start,int end)
{
    if(start>end)
        return;
    int left = start;
    int right =end;
    int temp = a.array[left];
    while(left<right)
    {
        while(a.array[right]>temp&&left<right)
        {
            right--;
        }
        if(left<right)
        {
            a.array[left++] = a.array[right];
        }
        while(a.array[left]<temp&&left<right)
        {
            left++;
        }
        if(left<right)
        {
            a.array[right--] = a.array[left];
        }
    }
    a.array[left] = temp;
    FastSort(a, start, left - 1);
    FastSort(a, right + 1, end);
}
void DynamicArray::DArrayFastSort(DynamicArray &a)
{
    FastSort(a, 0, size - 1);
}

DynamicArray DynamicArray::BinarySearch(const DynamicArray &a, ElementType element)
{
    int left = 0;
    int right = a.size - 1;
    while(left<=right)
    {
        int mid = left + (right - left) / 2;
        if(a.array[mid]<element)
        {
            left = mid + 1;
        }
        else if(a.array[mid]>element)
        {
            right = mid - 1;
        }
        else
        {
            return a.array[mid];
        }
    }
    
    return ElementType();
}
